package 力扣_链表.面试常考;

/**
 * @author zx
 * @create 2022-09-12 11:11
 */
public class 反转链表II {
    public ListNode reverseBetween(ListNode head, int left, int right) {
        ListNode dummyHead = new ListNode(501);
        dummyHead.next = head;
        ListNode prev = dummyHead;//待反转的前驱
        for(int i = 0;i < left - 1;i++){
            prev = prev.next;
        }
        ListNode temp = prev;
        ListNode start = prev.next;//待反转的第一个元素,反转后用于连接后续链表
        for(int i = left - 1;i < right;i++){
            temp = temp.next;
        }
        ListNode next = temp.next;//right之后的链表
        temp.next = null;//断开
        //连接
        prev.next = reverse(start);
        start.next = next;
        return dummyHead.next;
    }
    private ListNode reverse(ListNode head){
        ListNode prev = null;
        while(head != null){
            ListNode temp = head.next;
            head.next = prev;
            prev = head;
            head = temp;
        }
        return prev;
    }
}
